Mathematical Muffin Morsels: Nobody wants a Small Piece by William Gasarch Erik Metz Jacob Prinz and Daniel Smolyak

Author:William Gasarch, Erik Metz, Jacob Prinz and Daniel Smolyak
Language: eng
Format: epub
Publisher: World Scientific Publishing Co. Pte. Ltd.
Published: 2020-07-15T00:00:00+00:00

Chapter 10

The Easy Buddy–Match Method

10.1.Recap and Goals for This Chapter

From Chapters 4, 6, and 8 we know that, for m ≥ s,

Just for now we will refer to the min of those quantities as minf(m, s). Is it the case that, for all m ≥ s, f(m, s) = minf(m, s)? No. The counterexample with the smallest s is f(16, 15); however it is more illustrative to show the following:

(The first two results can be obtained by MID.)

The proof of the upper bounds uses a technique, which we call easy buddy–match (EBM). We develop an algorithm EBM(m, s) which, given m, s, outputs an α such that f(m, s) ≤ α. It only works when there are 2-shares (so V = 3). The key new idea is that if Alice is a 2-student and she has a share of size x, then her other share has size − x. This is called matching. It is similar to buddying where, if there is a share of size x, there is a share of size 1 − x.

Exercise 10.1. For (m, s) = (16, 15), (17, 16), (19, 18), (29, 27):

(1)Compute α = minf(m, s).

(2)Compute FINDPROC(m, s, α). (You should get a DK which means that minf(m, s) is unlikely to be f(m, s).)

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.